from pprint import pprint
# 背包问题

# 物品数量
n = 4
# 背包容量
bagV = 8

w = [0, 2, 3, 4, 5]
v = [0, 3, 4, 5, 6]
# 构造dp
dp = [[0] * (bagV + 1) for _ in range(n + 1)]

# 遍历行先, 从1开始遍历
for i in range(1, n + 1):
    for j in range(1, bagV + 1):
        # 判断新增的物品重量是否大于容量
        if j >= w[i]:
            # 可装，也不一定是最大，要比较
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
        else:
            # 无法装, 那就取上一个i-1的值
            dp[i][j] = dp[i - 1][j]
print(dp[n][bagV])

# 购物单
# 预算
budget = 50//10
# 物品购买数量
n = 5
# 物品价格
prices = [0, 2, 2, 1, 1, 1]
# 重要度
important = [0, 3, 3, 3, 2, 1]
# 属于谁的主件，0表示主件
tag = [0, 5, 5, 0, 0, 0]

# 题目约束价格为10的倍数
# list(range(10, budget+10, 10)) = [10, 20, 30, 40, 50]
# 需要多构造一个
dp = [[0] * (budget + 1) for _ in range(n+1)]
for i in range(1, n + 1):
    for j in range(1, budget + 1):
        try:
            if j >= prices[i]:
                # and (tag[i] == 0 or tag[i] < i):
                # 判断新增的是否是附件，是附件且已经买了主件才允许买
                # 是主件
                # 是附件，判断是否已经购买主件

                # 判断

                dp[i][j] = max(dp[i-1][j], dp[i-1][j-prices[i]] + important[i]*prices[i])
            else:
                dp[i][j] = dp[i-1][j]
        except:
            print("test")
            raise


pprint(dp)